// @Description 使用 Trie 树实现动态路由匹配
// @Author insight21
// @Since 2021/9/12

package web

import "strings"

type node struct {
	pattern  string  // 待匹配路径 /hello/:lang
	part     string  // 路径中的一部分 /:lang
	children []*node // 子节点
	isWild   bool    // 模糊匹配标志
}

// 插入节点 用于注册路由
func (n *node) insert(pattern string, parts []string, depth int) {
	if depth == len(parts) {
		n.pattern = pattern
		return
	}

	part := parts[depth]
	child := n.matchChild(part)

	// 如果匹配失败就新建一个
	if child == nil {
		child = &node{
			part:   part,
			isWild: part[0] == '*' || part[0] == ':',
		}
		n.children = append(n.children, child)
	}

	child.insert(pattern, parts, depth+1)
}

// 寻找节点 用于匹配路由
func (n *node) search(parts []string, depth int) *node {
	if depth == len(parts) || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[depth]
	children := n.matchChildren(part)

	for _, child := range children {
		search := child.search(parts, depth+1)
		if search != nil {
			return search
		}
	}

	return nil
}

// 匹配路径中的节点 遇到第一个就返回 用于插入
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.isWild || child.part == part {
			return child
		}
	}
	return nil
}

// 匹配路径中的节点 返回所有成功节点 用于查找
func (n *node) matchChildren(part string) []*node {
	ret := make([]*node, 0)
	for _, child := range n.children {
		if child.isWild || child.part == part {
			ret = append(ret, child)
		}
	}
	return ret
}
